People are increasingly using computing devices to access information of a variety of types, including to access information over networks from remote devices and services (e.g., over the Internet and/or private networks, such as communications networks of cellular telephone service providers). One example of information that is often accessed and used includes various types of geographical information, such as maps and driving directions. In addition, many users of computing devices may desire to search for or otherwise locate various types of information in a geographic area near the user, including based on a particular location of the user (e.g., to search for pizza restaurants near my current location)—in some circumstances, such activities may be referred to as “local search” or more generally as location-based information access. In many local search scenarios, user requests are made to find all examples of X within Y miles of a point P. For example, a request may be made by a user to find all Starbucks locations within 5 miles of my current location, or to find all coffee shops open until at least 10 pm within 2 miles of a point P, with the search results ordered by distance from P. Such users may use a variety of types of computing devices when accessing information, including both fixed-location computing devices (e.g., desktop computers) and mobile computing devices (e.g., laptop computers; handheld computers and/or communications devices, including cellular telephones with data communication capabilities; vehicle-based devices; etc.).
The ability of users to receive such location-based information provides a variety of benefits to the users if the information is accurate. However, various problems exist with current techniques for providing such information. As one example, current providers of location-based information typically do not consider any actual travel-related information when providing location-based information. In particular, if a user requests information near a particular origination point location, current providers will typically define and use an ‘as-the-crow-flies’ circular search radius in the spatial search domain around the origination point of the user. This method produces search results which may be within a specified geographical distance, but to which the actual travel distance may be significantly larger. As an example, consider the case of the Seattle-Bellevue area of the Puget Sound region of Washington State in the United States. The area is divided in the east-west direction by Lake Washington, which has two bridges to cross the lake. Accordingly, a geographic radius-based ‘nearest search’ query may result in recommendations of “nearest” targets which by actual travel distance are much further than other viable destinations. This phenomenon is illustrated in FIG. 1 via a search for “Toys ‘R’ Us” retail store locations within ten miles of the origination point 105 (indicated by pushpin 1 in the figure, and labeled as ‘Start Point’ in the legend 150), and corresponding to a location south of Lake Union in Seattle. In this case, by naive as-the-crow-flies geographic radius search (which typically corresponds to great circle route distances), the Toys ‘R’ Us store in Bellevue, Wash. (shown on the map 100 as the rectangular brown box 110a with a number 1 and a lower triangle-shaped protrusion, and represented in the legend as the red rectangular box 110b with a number 3) is the closest to the origination point, and in particular is shown as being roughly 6.6 miles away. Conversely, the Toys ‘R’ Us store in the Northgate area of Seattle (shown on the map as the rectangular brown box 120a with a number 2 and a lower triangle-shaped protrusion, and represented in the legend as the red rectangular box 120b with a number 2) is roughly 6.9 miles away using an as-the-crow-flies geographic distance. However, the actual driving distance to the Toys ‘R’ Us store in Bellevue from the origination point is roughly 10.8 miles via the limited routes available across Lake Washington (e.g., across the Interstate 90 freeway bridge 130 or the State Highway 520 bridge 140), whereas the Toys ‘R’ Us store in Northgate is roughly 7.2 miles in actual driving distance from the origination point.